package leetcode.editor.cn.q1_300.q50;

import java.util.HashMap;
import java.util.Map;

/**
 * 看的官方答案
 *
 * @author qidi
 * @date 2021-12-23 14:36:30
 */
class Q0087_ScrambleString {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        String s1, s2;
        // 记忆化搜索存储状态的数组
        // -1 表示 false，1 表示 true，0 表示未计算
        int[][][] memo;

        public boolean isScramble(String s1, String s2) {

            if (s1.length() == 1) return s1.equals(s2);

            if (s1.length() != s2.length()) return false;

            int len = s1.length();
            this.memo = new int[len][len][len + 1];
            this.s1 = s1;
            this.s2 = s2;

            return process(0, 0, len);
        }

        // 第一个字符串从 i1 开始，第二个字符串从 i2 开始，子串的长度为 length，是否和谐
        private boolean process(int i1, int i2, int len) {
            if (memo[i1][i2][len] != 0) {
                return memo[i1][i2][len] == 1;
            }

            // 判断两个子串是否相等
            if (s1.substring(i1, i1 + len).equals(s2.substring(i2, i2 + len))) {
                memo[i1][i2][len] = 1;
                return true;
            }

            if (!checke(i1, i2, len)) {
                memo[i1][i2][len] = -1;
                return false;
            }

            for (int i = 1; i < len; i++) {
                // 不交换
                if (process(i1, i2, i) && process(i1 + i, i2 + i, len - i)) {
                    memo[i1][i2][len] = 1;
                    return true;
                }
                // 交换
                if (process(i1, i2 + len - i, i) && process(i1 + i, i2, len - i)) {
                    memo[i1][i2][len] = 1;
                    return true;
                }
            }

            memo[i1][i2][len] = -1;
            return false;
        }

        private boolean checke(int i1, int i2, int len) {
            Map<Character, Integer> freq = new HashMap<Character, Integer>();
            for (int i = i1; i < i1 + len; ++i) {
                char c = s1.charAt(i);
                freq.put(c, freq.getOrDefault(c, 0) + 1);
            }
            for (int i = i2; i < i2 + len; ++i) {
                char c = s2.charAt(i);
                freq.put(c, freq.getOrDefault(c, 0) - 1);
            }
            for (Map.Entry<Character, Integer> entry : freq.entrySet()) {
                int value = entry.getValue();
                if (value != 0) {
                    return false;
                }
            }
            return true;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0087_ScrambleString().new Solution();
        System.out.println(solution.isScramble("eebaacbcbcadaaedceaaacadccd", "eadcaacabaddaceacbceaabeccd"));
        System.out.println(solution.isScramble("abcdbdacb", "bdacabcdb"));
        System.out.println(solution.isScramble("abcdbdacbdac", "bdacabcdbdac"));
        System.out.println(solution.isScramble("dbdac", "abcdd"));
        System.out.println(solution.isScramble("abb", "bab"));
        System.out.println(solution.isScramble("abc", "cab"));
        System.out.println(solution.isScramble("ab", "ba"));
        System.out.println(solution.isScramble("abcd", "bdac"));
        System.out.println(solution.isScramble("abcde", "aecdb"));
        System.out.println(solution.isScramble("abcde", "caebd"));
    }
}